Key establishment is the process by which two (or more) entities establish a shared secret key.
The key is subsequently used to achieve some cryptographic goal, such as confidentiality or data integrity. Ideally, the established key should have precisely the same attributes as a key established face-to-face it should be distributed uniformly at random from the key space, and no unauthorized (and computationally bounded) entity should learn anything about the key.
Broadly speaking, there are two kinds of key establishment protocols: key transport protocols in which a key is created by one entity and securely transmitted to the second entity, and key agreement protocols in which both parties contribute information which jointly establish the shared secret key.
Let A and B be two honest entities, i.e., legitimate entities who execute the steps of a protocol correctly. Informally speaking, a key agreement protocol is said to provide implicit key authentication (of B to A) if entity A is assured that no other entity aside from a specifically identified second entity B can possibly learn the value of a particular secret key Note that the property of implicit key authentication does not necessarily mean that A is assured of B actually possessing the key. A key agreement protocol which provides implicit key authentication to both participating entities is called an authenticated key agreement (AK) protocol.
Informally speaking, a key agreement protocol is said to provide explicit key confirmation (of B to A) if entity A is assured that the second entity B has actually computed the agreed key. The protocol provides implicit key confirmation if A is assured that B can compute the agreed key. While explicit key confirmation appears to provide stronger assurances to A than implicit key confirmation (in particular, the former implies the latter), it is possible that, for all practical purposes, the assurances are in fact the same. This is because B may delete the key immediately after the explicit key confirmation process.
If both implicit key authentication and (implicit on explicit) key confirmation (of B to A) are provided, then the key establishment protocol is said to provide explicit key authentication (of B to A). A key agreement protocol which provides explicit key authentication to both participating entities is called an authenticated key agreement with key confirmation (AKC) protocol.
An unknown key-share (UKS) attack on an AK or AKC protocol is an attack whereby an entity A is coerced into sharing a key with an entity B without A's knowledge, i.e., when A believes the key is shared with some entity E≠B. Notice that if an AK or AKC protocol succumbs to a UKS attack, then this does not contradict the implicit key authentication property of the protocol. By definition, the provision of implicit key authentication is only considered in the case where A engages in the protocol with an honest entity (which E isn't).
The station-to-station (STS) protocol is a Diffie-Hellman-based AKC protocol that purports to provide both (mutual) implicit key authentication and (mutual) key confirmation, and additionally appears to possess desirable security attributes such as forward secrecy and key-compromise impersonation. There are two main variants of STS as described in W. Diffie et al., “Authentication and authenticated key exchanges”, Designs, Codes and Cryptography, 2 (1992) 107-125. One in which key confirmation is provided by using the agreed key K in a MAC algorithm (STS-MAC), and another in which K is used in an encryption scheme (STS-ENC). STS-MAC is preferred over STS-ENC in many practical scenarios. Moreover, the use of encryption to provide key confirmation in STS-ENC is suspect—the goal of an encryption scheme is to provide confidentiality, rather than as an authentication mechanism for proving possession of a key. One advantage of STS-ENC over STS-MAC is that the former can facilitate the provision of anonymity.
Many protocols related to STS have appeared in the literature. It should be noted, however, that these protocols cannot be considered minor variants of STS.
For the sake of clarity, notation used in the specification, is initially outlined as follows:
A, BHonest entities.EThe adversary.SAA's (private) signing key for a signature scheme S.PAA's (public) verification key for S.SA(M)A's signature on message M.CertaA's certificate containing A's name. A's public signaturekey PA, and possibly some other information.EK(M)Encryption of M using a symmetric-key encryption schemewith key KMACK(M)Message authentication code of M under key K.G, α, nDiffie-Hellman parameters; α is an element of prime order nin the finite group G.rAA's ephemeral Diffie-Hellman private key; 1 ≦ rA ≦ n − 1.KEphemeral Diffie-Hellman shared secret, K = α‘1’aThe two STS variants are presented below. In both descriptions, A is called the initiator, while B is called the responder.STS-MAC protocolThe STS-MAC protocols is depicted below. Initiator A selects a random secret integer rA, 1≦rA≦n−1, and sends to B the message (1). Upon receiving (1), B selects a random secret integer rB,1≦rB≦n−1, computes the shared secret K=αrArB, and sends message (2) to A. Upon receiving (2), A uses CertB to verify the authenticity of B's signing key PB, verifies B's signature on the message (αrB, αrA), computes the shared secret K, and verifies the MAC on SB(αrB, αrA) A then sends message (3) to B. Upon receipt of (3), B uses CertA to verify the authenticity of A's signing key PA, verifies A's signature on the message (αrA, αrB) and verifies the MAC on SB(αrA, αrB). If at any stage a check or verification performed by A or B fails, then that entity terminates the protocol run, and rejects.                (1) A→B A, αrA         (2) A←B CertB, αrB,(SB(αrB,αrA),MACK(SB(αrB,αrA))        (3) A→B CertA, SA(αrA,αrB),MACK(SA(αrA,αrB))STS-ENC protocolThe STS-ENC protocol is given below. For the sake of brevity, the checks that should be performed by A and B are henceforth omitted.        (1) A→B A, αrA         (2) A←B CertB, αrB, EK(SB(αrB,αrA))        (3) A→B CertA, EK(SA(αrA,αrB))        
In order to more clearly understand an unknown key-share (UKS) attack on a key agreement protocol, we consider a hypothetical scenario where a UKS attack can have damaging consequences. Suppose that A is a bank branch and B is an account holder. Certificates are issued by the bank headquarters and within each certificate is the account information of the holder. Suppose that the protocol for electronic deposit of funds is to exchange a key with a bank branch via an AKC protocol. At the conclusion of the protocol run, encrypted funds are deposited to the account number in the certificate. Suppose that no further authentication is done in the encrypted deposit message (which might be the case to save bandwidth). If the UKS attack mentioned above is successfully launched then the deposit will be made to E's account instead of B's account.
It is important to observe that a UKS attack on an AKC protocol is a much more serious consideration than a UKS attack on an AK protocol (which does not provide key confirmation).
No key agreed in an AK protocol should be used without key confirmation. Indeed, some standards take the conservative approach of mandating key confirmation of keys agreed in an AK protocol. If appropriate key confirmation is subsequently provided, then the attempt at a UKS attack will be detected. For this reason, the above hypothetical scenario (in particular, the assumption that no further authentication is performed after termination of the key agreement protocol) is realistic if an AKC protocol is used (since key confirmation has already been provided), an unrealistic if an AK protocol is used (since key confirmation has not yet been provided).
In a UKS attack against the responder, the adversary E registers A's public key PA as its own; i.e., PE=PA. When A sends B message (1), E intercepts it and replaces the identity A with E. E then passes message (2) from B to A unchanged. Finally E intercepts message (3), and replaces CertA with CertE. Since PA=PE, we have SA(αrA,αrB)=SE(αrA,αrB). Hence, B accepts the key K and believes that K is shared with E, while in fact it is shared with A. Note that E does not learn the value of K. The attack is depicted below. The notation A!→B means that A transmitted a message intended for B, which was intercepted by the adversary and not delivered to B.                (1) A!→B A,αrA         (1′) E→B E, αrA         (2) E←B CertB, αrB,SB(αrB,αrA),MACK(SB(αrB,αrA))        (2′) A←E CertB, αrB,SB(αrB,αrA),MACK(SB(αrB,αrA))        (3) A!→B CertA, SA(αrB,αrA),MACK(SA(αrB,αrA))        (3′) E→B CertA, SA(αrB,αrA),MACK(SA(αrB,αrA))        
Entity E can similarly launch a UKS attack against the initiator A by registering B's public key PB as its own. The attack is depicted below.                (1) A→E A,αrA         (1′) E→B A, αrA         (2) A←!B CertB, αrB,SB(αrB,αrA),MACK(SB(αrB,αrA))        (2′) A←E CertE, αrB,SB(αrB,αrA),MACK(SB(αrB,αrA))        (3) A→E CertA, SA(αrB,αrA),MACK(SA(αrB,αrA))        (3′) E→B CertA, SA(αrB,αrA),MACK(SA(αrB,αrA))        
In describing new on-line UKS attacks we make the following assumptions. First, we assume that the signature scheme S used in STS has the following duplicate-signature key selection property. Suppose that PA (A's public key), and A's signature sA on a message M are known. Then the adversary is able to select a key pair (PE, SE) with respect to which sA is also E's signature on the message M.
Second, E is able to get its public key certified during a run of the STS protocol. This assumption is plausible, for instance, in situations where delays in the transmission of messages are normal, and where the CA is on-line.
This new UKS attack against the responder is similar to the public key substitution attack against the responder as described earlier. After A sends message (3), E intercepts it and selects a key pair (PE,SE) for the employed signature scheme such that SE(αrA,αrB)=SA(αrA,αrB). E then obtains a certificate CertE for PE, and transmits message (3′) to B.
This new UKS attack against the initiator is similar to the public key substitution attack against the initiator described above. After B sends message (2), E intercepts it and selects a key pair (PE; SE) for the employed signature scheme such that SE SB(αrB,αrA)=SB(αrB,αrA). E then obtains a certificate CertE for PE, and transmits message (2′) to A.
In the on-line UKS attacks, the adversary knows the private key SE corresponding to its chosen public key PE. Hence, unlike the case of public key substitution attacks, the on-line attacks cannot be prevented by requiring that entities prove to the certificate-issuing authority possession of the private keys corresponding to their public keys during the certification process.
The applicants have discovered that the STS protocols have some security attributes that are lacking. It is, thus desirable to implement a STS protocol wherein unknown key-share attacks are minimized.